/**
 * https://leetcode.cn/problems/count-number-of-texts/submissions/563616140/
 * 2266.统计打字方案数
 * medium 2024.09.11
 * 多维dp
 */

class Solution {
public:
    typedef long long ll;
    ll mod=1e9+7;
    int countTexts(string pressedKeys) {
        ll sum=1;
        vector<ll>dp3={1,1,2,4};
        vector<ll>dp4={1,1,2,4};
        int n=pressedKeys.size();
        for(int i=4;i<=n;++i){
            dp3.push_back(((dp3[i-1]%mod)+(dp3[i-2]%mod)+(dp3[i-3]%mod))%mod);
            dp4.push_back(((dp4[i-1]%mod)+(dp4[i-2]%mod)+(dp4[i-3]%mod)+(dp4[i-4]%mod))%mod);
        }
        for(int i=0;i<n;++i){
            int k=1;
            while(i<n-1&&pressedKeys[i]==pressedKeys[i+1]){
                i++;
                k++;
            }
            if(pressedKeys[i]=='7'||pressedKeys[i]=='9')
            sum=((sum%mod)*(dp4[k]%mod))%mod;
            else
            sum=((sum%mod)*(dp3[k]%mod))%mod;
        }
        return sum%mod;
    }
};